/*
伸展树比较简单，其主要操作同普通二叉搜索树；
在访问一个节点时，对这个节点沿着上游路线调整，直至调整到根节点；
在删除一个节点时，先调整至跟节点，在删除该根节点即可。
*/

#ifndef _SPLAYTREE_H_

#define _SPLAYTREE_H_

#include <stdio.h>
#include <stdlib.h>

#define ElementType int

struct TreeNode;
typedef struct TreeNode* SplayTree;
typedef struct TreeNode* Position;

SplayTree Insert(SplayTree tree, ElementType data);
SplayTree Delete(SplayTree tree, ElementType data);
void MakeEmpty(SplayTree tree);

Position FindMax(SplayTree tree);
Position FindMin(SplayTree tree);
Position Find(SplayTree tree, ElementType data);

void PreOrder(SplayTree tree);
void InOrder(SplayTree tree);
void PostOrder(SplayTree tree);

Position AdjustTree(SplayTree tree, Position node);

void testSplayTree();

#endif
